//重排链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* ReverseList(ListNode* head)
    {
        ListNode* newlist = new ListNode;
        newlist->next = nullptr;
        while(head)
        {
            ListNode* next = newlist->next;
            newlist->next = head;
            ListNode* temp = head->next;
            head->next = next;
            head = temp;
        }
        ListNode* ret = newlist->next;
        delete newlist;
        return ret;
    }
    void reorderList(ListNode* head) {
        if(head->next == nullptr) return;
        //快慢双指针定位出两个链表
        ListNode* fast = head;
        ListNode* slow = head;
        ListNode* newhead = new ListNode;
        newhead->next = head;
        head = newhead;
        ListNode* prev = head;
        while(fast && fast->next)
        {
            fast = fast->next->next;
            prev = slow;
            slow = slow->next;
        }
        //逆序slow所指链表
        prev->next = nullptr;
        ListNode* head2 = ReverseList(slow);
        //合并head和head2
        ListNode* cur1 = head->next;
        ListNode* cur2 = head2;
        ListNode* temp;
        while(cur1 && cur2)
        {
            ListNode* next1 = cur1->next;
            ListNode* next2 = cur2->next;
            cur1->next = cur2;
            cur2->next = next1;
            temp = cur2;
            cur1 = next1;
            cur2 = next2;
        }
        if(cur2) 
            temp->next = cur2;
        ListNode* del = head;
        head = head->next;
        delete del;
    }
};

//两两交换链表中的节点
// /**
//  * Definition for singly-linked list.
//  * struct ListNode {
//  *     int val;
//  *     ListNode *next;
//  *     ListNode() : val(0), next(nullptr) {}
//  *     ListNode(int x) : val(x), next(nullptr) {}
//  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
//  * };
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* temp = dummyHead;
        while (temp->next != nullptr && temp->next->next != nullptr) {
            ListNode* node1 = temp->next;
            ListNode* node2 = temp->next->next;
            temp->next = node2;
            node1->next = node2->next;
            node2->next = node1;
            temp = node1;
        }
        ListNode* ans = dummyHead->next;
        delete dummyHead;
        return ans;
    }
};

//两数相加
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rethead;
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        rethead = new ListNode;
        rethead->next = nullptr;
        ListNode* cur = rethead;
        int next = 0;
        while(l1 || l2)
        {
            int l1val = 0 , l2val = 0;

            if(l1) l1val = l1->val;
            if(l2) l2val = l2->val;

            int val = l1val + l2val + next;
            if(val > 9)
            {
                next = 1;
                val -= 10;
            }
            else 
            {
                next = 0;
            }
            ListNode* newnode = new ListNode(val);
            ListNode* nextnode = cur->next;
            newnode->next = nextnode;
            cur->next = newnode;
            cur = newnode;
            if(l1) l1 = l1->next;
            if(l2) l2 = l2->next;
        }
        if(next)
        {
            ListNode* newnode = new ListNode(next);
            ListNode* nextnode = cur->next;
            newnode->next = nextnode;
            cur->next = newnode;
        }
        return rethead->next;
    }
};